As integrated circuits are produced with greater and greater levels of circuit density, efficient testing schemes that guarantee high fault coverage while minimizing test costs and chip area overhead have become essential. The number of transistors that can be placed on a chip has been doubling roughly every eighteen months, as predicted by Moore's law. The amount of data required to test such massively complex chips has been increasing even more rapidly. In practical terms, for very large integrated circuits, the test cost is approaching (and may even exceed) the design cost. To address the rapid increase in volume of test data, a number of compression schemes have been developed.
Many integrated circuits are tested using structured design-for-testability (“DFT”) techniques, which employ the general concept of making some or all state variables (e.g., memory elements such as flip-flops and latches) directly controllable and observable. Preferably, a circuit is treated, as far as testing of combinational faults is concerned, as a combinational or a nearly combinational network. The most-often used DFT methodology assumes that during testing all (or almost all) memory elements are connected into one or more shift registers termed “scan chains.” See, e.g., U.S. Pat. No. 4,503,537.
A circuit that utilizes scan chains for testing typically has two basic modes of operation: a normal mode, and a test (or scan) mode. In the normal mode, the memory elements perform their regular functions. In the scan mode, the memory elements become scan cells that are connected to form a number of scan chains. These scan chains are used to shift a set of test patterns into the circuit and to shift out circuit (or test) responses to the test patterns. The test responses are then compared to fault-free responses to determine if the circuit-under-test (“CUT”) works properly.
Scan design methodology has gained widespread adoption by virtue of its simple automatic test pattern generation (“ATPG”) and silicon debugging capabilities. Today, ATPG software tools are so efficient that it is possible to generate test sets (a collection of test patterns) that guarantee almost complete fault coverage of several types of fault models including stuck-at and transition faults. It is also possible to target other fault models such as path delay and bridging faults. Typically, when a particular potential fault in a circuit is targeted by an ATPG tool, only a small number of scan cells (e.g., 2-5%) need to be specified to detect the particular fault. These scan cells are termed “deterministically specified cells.” The remaining scan cells in the scan chains can then be filled with random binary values, which are termed “randomly specified cells.” This results in a pattern that is fully specified, that is more likely to detect additional faults, and that can be stored on a tester.
FIG. 1 is a block diagram of a conventional system 100 for testing digital circuits with scan chains. Two-input XOR gates, in this and subsequent figures, are represented by a circle inscribed with a cross 112. During a typical scan mode, external automated test equipment (“ATE”) or tester 102 applies a set of fully specified test patterns 104 to a CUT 106 via scan chains 108 within the circuit. Once the scan chains 108 have been loaded with the test patterns 104, the CUT 106 is run in normal mode using the test patterns for input values. The CUT 106 may be run for a designated period of time (e.g., one clock cycle) after which the test responses to the test patterns are stored in the scan chains 108. With the circuit again in scan mode, the test responses are routed back to the tester 102, which compares the captured test responses with fault-free reference responses 110. A significant limitation of this approach is that it requires an expensive, memory-intensive tester and a long test time to test a complex circuit. For example, it has been reported that the volume of test data can exceed one kilobit per single logic gate in a large design. It is undesirable to test large circuits using this method, as it is difficult to store the large number of test patterns required, and the test application itself is too time intensive.
These limitations of time and storage can be overcome to some extent by adopting a built-in self-test (“BIST”) framework as shown in FIG. 2. In BIST, additional on-chip circuitry is included to generate test patterns, evaluate test responses, and control the test. For example, a pseudo-random pattern generator 200 (“PRPG”) is used to generate the test patterns instead of storing deterministic test patterns. Additionally, a multiple input signature register (“MISR”) 202 can be used to generate and store a resulting signature from the test responses. MISRs, such as the one shown in FIG. 5, compress the data and generate a signature based on the scan chain input 502, and feedback 504, 506.
Due to the high volume of test data that needs to be processed in a CUT, compactors are often used to compress the test responses from the scan chains. This greatly simplifies determining if the circuit has flaws and the location of any problems that are discovered. Currently-available test response compaction schemes can be grouped into two classes: (1) infinite input response compaction schemes (also known as “time compactors”); and (2) space compaction schemes (also known as “space compactors” or “linear compactors”).
Time compactors typically have a feedback structure with memory elements for storing a signature, which represents the results of the test. After the signature is completed, it is read and compared to a fault-free signature to determine if an error exists in the circuit-under-test. Time compactors may use polynomial division, counting-based techniques, and check-sum-based methods, and are typically employed in BIST applications. The actual compaction is usually performed by linear finite state machines, such as a linear feedback shift register (“LFSR”), a MISR, or cellular automata. These schemes are capable of compacting gigabits of test response data into a small signature that is typically 32-, 64-, or 128-bits long, thereby achieving compaction ratios between 106 and 108. This is possible because an error, once injected into this type of compactor, remains there until another group of errors erases it in the rare case of aliasing. The infinite input response compaction schemes suffer from a number of disadvantages. In particular, this type of compaction scheme cannot handle any unknown states in the test response. Because these systems all include feedback, an unknown state will circulate in the compactor endlessly until the compactor is reset. Thus, all states can become unknown after a few cycles, thereby corrupting the test signature and rendering the test useless. Fault diagnosis is also more complicated as it requires multiple passes with direct access to pre-compacted responses.
LFSRs are among the most popular time compactors used in integrated circuits. An LFSR produces pseudo-random test sequences. In its basic form, the LFSR (shown in FIG. 3) is modified to accept an external input in order to act as a polynomial divider. An alternative implementation is shown in FIG. 4. The input sequence, represented by a polynomial, is divided by the characteristic polynomial of the LFSR. As the division proceeds, the quotient sequence appears at the output of the LFSR and the remainder is kept in the LFSR. Once testing is completed, the content of the LFSR can be treated as a signature.
FIG. 5 shows another time compactor (which is a natural extension of the LFSR-based compactor) called a multiple-input LFSR, also known as a multiple-input signature register or MISR. A MISR may be used to test circuits in a multiple scan chain environment as shown in FIG. 5. MISRs feature a number of XOR gates coupled to the CUT scan-chain outputs and to the flip-flops of the shift register.
In contrast to time compactors, which employ memory elements in their compaction schemes, space compactors comprise combinational circuits that are predominantly built from XOR networks. The XOR network is configured to generate n test outputs from m primary outputs of the CUT, where n<m. Space compactors typically offer smaller compaction ratios than time compactors, but can handle some unknown states in the test responses without circuit modification. Another difference between spatial compactors and time compactors is that the output value of a spatial compactor will change with a change in just one input to the compactor, making single errors observable that would be undetectable after compression in a time compactor. With time compactors, a change in an input value may be obscured by the compression, and therefore go undetected at the output of the compactor. Even spatial compactors, however, may mask errors. For example, one basic characteristic of an XOR (parity) tree as typically used in a spatial compactor is that any odd-numbered combination of errors on its inputs will propagate to the outputs, but any even-numbered combination of errors will remain undetected. For instance, when the spatial compactor reads two errors at the same time, the multiple errors may cancel each other out so that the compressed signature of the faulty circuit mimics that of a fault-free circuit. This phenomenon is known as “error masking” or “aliasing” since it involves a first error state value erasing a second error state value. Aliasing is often measured in terms of its likelihood of occurrence.
Spatial compactors can be customized for a given CUT to reduce the aliasing phenomenon, such as shown in the U.S. Pat. No. 5,790,562, based on multiplexed parity trees or nonlinear trees comprising elementary gates such as AND, OR, NAND, and NOR gates. FIG. 6 shows one example of a modified spatial compactor. In particular, FIG. 6 shows a pipelined spatial compactor that includes a bank of flip-flops separating stages of XOR gates. A clock (not shown) controls the flip-flops and allows a one-cycle delay before reading the compacted output. Another spatial compaction technique, known as the X-compact scheme, has recently been proposed. See S. Mitra and K. S. Kim, “X-Compact: An Efficient Response Compaction Technique for Test Cost Reduction,” Proc. ITC, pp. 311-320 (Oct. 2002). A so-called “X-compactor” is understood to have no memory and no feedback. Thus, the output of the X-compactor is indicative of the current X-compactor input, and any error present at the output is clocked out after a single clock cycle. As more fully explained below, however, the amount of compaction that can be realized in an X-compact scheme is severely limited by the number of compactor outputs.
For any of the spatial compactors described above, the presence of unknown states can also be problematic for accurate error detection. For example, an unknown state on one or more inputs of an XOR tree generates unknown values at its output, consequently masking the propagation of any faults at the other inputs. Thus, one limitation of spatial compactors, such as the X-compactor and the compactor of FIG. 6, is that unknown states can reduce fault coverage. Moreover, time compactors, such as shown in FIGS. 3, 4, and 5, are restricted in their ability to handle unknown states since an unknown state on any input can corrupt the compressed output generated by the compactor. Additionally, if an error is detected within the integrated circuit, both spatial and time compactors have a limited ability to localize the fault.